package uniquepath62

// https://leetcode-cn.com/problems/unique-paths/
// 思路：
// 动态规划实现：
// 1. 定义状态：dp[i][j]表示到达第i行第j列的方法数
// 2. 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
// 3. 初始状态：dp[0][0] = 1
// 4. 返回值：dp[m-1][n-1]
// 复杂度：O(m*n)
// 空间复杂度：O(m*n)
func uniquePaths(m int, n int) int {
	// 如果行数或者列数为0，返回0
	if m == 0 || n == 0 {
		return 0
	}
	// 如果只有一行或者一列，只有一种方法
	if m == 1 || n == 1 {
		return 1
	}
	// 创建一个二维数组dp，大小为m*n
	// dp[i][j]表示到达第i行第j列的方法数
	// dp[0][0] = 1
	// dp[i][j] = dp[i-1][j] + dp[i][j-1]
	// dp[i][0] = 1
	// dp[0][j] = 1
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	dp[0][0] = 1
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i == 0 && j == 0 {
				continue
			}
			if i == 0 {
				dp[i][j] = dp[i][j-1]
			}
			if j == 0 {
				dp[i][j] = dp[i-1][j]
			}
			if i > 0 && j > 0 {
				dp[i][j] = dp[i-1][j] + dp[i][j-1]
			}
		}
	}
	return dp[m-1][n-1]
}

// 优化
// 其实我们只需要一维数组就可以了
// 1. 定义状态：dp[j]表示到达第i行第j列的方法数
// 2. 状态转移方程：dp[j] = dp[j-1] + dp[j]
// 3. 初始状态：dp[0] = 1
// 4. 返回值：dp[n-1]
// 复杂度：O(m*n)
// 空间复杂度：O(n)
func uniquePaths_optimized(m int, n int) int {
	// 如果行数或者列数为0，返回0
	if m == 0 || n == 0 {
		return 0
	}
	// 如果只有一行或者一列，只有一种方法
	if m == 1 || n == 1 {
		return 1
	}
	// 创建一个一维数组dp，大小为n
	// dp[j]表示到达第i行第j列的方法数
	// dp[0] = 1
	// dp[j] = dp[j-1] + dp[j]
	dp := make([]int, n)
	dp[0] = 1
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if j > 0 {
				dp[j] += dp[j-1]
			}
		}
	}
	return dp[n-1]
}
